The present invention relates to computer graphics. More specifically, the present invention relates to techniques for creating and using interior coordinates.
Character articulation (sometimes called rigging) is an important component of animation systems, particularly the high-end kind used in feature film production. Most modern high-end systems, such as AutoDesk and Maya, offer a variety of articulation methods. Some examples of these articulation methods are enveloping, shape blending, and chains of arbitrary deformations.
In the realm of deformations, free-form deformation methods are particularly popular due to a number of advantages. First, free-form deformation methods offer smooth and intuitive control over the motion of the character using only a few parameters, namely, the locations of the free-form lattice control points. Second, there are virtually no restrictions on the three-dimensional model of the character. Typically, the only requirement is that the character model be completely enclosed by the control lattice. The above two advantages generally allow one to decouple the resolution of the control lattice from that of the character being deformed. The resolution of the lattice is chosen to match the amount of detail necessary in the deformation, whereas the resolution of the character model is chosen to capture the static detail of the character. Additionally, one can control the deformation of the same character model with a hierarchy of lattices, thereby allowing for multi-resolution articulation—a highly desirable component of a character articulation system.
However, free-form deformation methods come with some inconvenient drawbacks. Articulating a multi-limbed character is best accomplished using a lattice that conforms to the geometry of the character. However, given the topological rigidity of a lattice, it is often necessary to combine several overlapping lattices, and each of the lattices possesses interior points that can be difficult and annoying to articulate. Some attempts have been made to generalized lattices to arbitrary volume meshes, but these attempts required the introduction and articulation of interior control points, adding to the difficulty and complexity of animation.
Other attempts introduce an even more topologically flexible method where the character or object to be deformed is positioned relative to a coarse closed triangular surface mesh. The coarse closed triangular surface mesh is referred to as a “cage.” The object is then “bound” to the cage by computing a weight at each cage vertex that is evaluated at the position of every point on the object. FIGS. 1A and 1B depict deformations of a simple object 110 bounded by a cage 120 generally in the prior art. FIG. 1A depicts simple object 110 bounded by cage 120 having a plurality of boundary points or vertices, including vertex 130. FIG. 1B depicts deformation of object 110 shown in FIG. 1A. As the cage vertices are moved to new locations to deform or articulate object 110, the deformed points for object 110 are computed from weights at each vertex of cage 120. FIG. 1B shows how, in this example, as vertex 130 is moved from lower right to upper left, object 110 is deformed resulting in object 140.
The weights at each cage vertex are generally known as generalized barycentric coordinates. One attempt for using generalized barycentric coordinate formulations is called Mean value coordinates (MVC). Mean value coordinates are particularly useful because the cage or cages that control deformation of an object can be any simple closed polygon in two dimensions, and any simple closed triangular mesh in three dimensions. Accordingly, mean value coordinates are also particularly interesting in the context of character articulation because the cage that controls the deformation can be any closed triangular surface mesh, so there is a great deal of topological and geometric flexibility when designing the cage. In addition, the mean value coordinates are smooth, so the deformation of the object is also smooth. Moreover, mean value coordinates reproduce linear functions, so the object does not “pop” when it is bound to the cage.
However, problems with methods using mean value coordinates are demonstrated with the articulation of bipedal character objects. Mean value coordinates lack non-negativity and interior locality. These two properties highly facilitate high-end character articulation. In regards to interior locality, the coordinates should fall off as a function of the distance between cage points and object points, where distance is measured within the cage. In regards to non-negativity, if an object point whose coordinate relative to a cage point is negative, it will move in the direction opposite to that cage point.
FIGS. 2A and 2B depict deformations of a bipedal character object 210 based on articulation of a cage 220 using mean value coordinates generally in the prior art. FIG. 2A depicts cage 210 having a plurality of vertices (e.g., vertex 220). In general, using mean value coordinates to provide deformation of bipedal character object 210, boundary points or vertices, such as vertex 230, that are modified on cage 220 influence the position of points on bipedal character object 210 in undesirable manners. For example, FIG. 2B depicts articulation of bipedal character object 230 shown in FIG. 2A using mean value coordinates. In this example, deformation of the left leg of bipedal character object 230 causes undesirable deformation to the right leg. As shown in FIG. 2B, deformation of the left leg using vertex 230 deforms the original bipedal character object 210 into bipedal character object 240.
FIG. 2B further shows how modified cage points (e.g., vertex 230) on the left leg significantly influence the position of object points along path 250 in the leg on the right. These undesirable effects typically occur because mean value coordinates are based on Euclidean (or straight-line) distances between points of the closed polygon and points of the model. Since the distance between the vertex 230 and the object points along path 250 in the leg on the right are relatively small in the bind pose, the influence is relatively large. This is because using mean value coordinates, distance between cage points and object points falls off using straight-line measurements, but not as distances measured within the cage. FIG. 2B further shows that the displacement of the object points along path 250 in the right leg is in a direction opposite to the displacement of vertex 230. This occurs because the mean value coordinates are negative. Although the influence is noticeable in still images, the undesirable movement of points on models is evident in interactive use and is highly undesirable for the articulation of characters in feature film production.
Accordingly, what is desired are improved methods and apparatus for solving the problems discussed above, while reducing the drawbacks discussed above.